/**
 * NOTE: 并查集(由孩子指向父亲): 处理连接问题, 路径问题, 类似数学中的多个集合的并集
 * 比如: 网络中节点间的连接状态, 网络是一个抽象的概念,
 * 用户之间形成的网络, 微博, 社交形成的网络, 信息网络, 交通, 航班,
 * 给出任意的两个点, 问是否可以连接起来
 */

// 并查集没有更新,删除和添加的操作, 抽象编号数据, 那么在并查集中只存储编号(id)
interface UF {
  isConnected(p: number, q: number): boolean
  unionElements(p: number, q: number): void
  getSize(): number
}

// 每个元素只有一个指针, 指向父亲节点
export class UnionFindTree implements UF {

  private parent: number[] = []

  // 表示 sz[i] 表示以 i 为根的集合中元素的个数, 为了防止树退化为链表, 使用 sz 进行优化
  private sz: number[] = []

  // 最大深度, rank[i] 表示根节点为 i 的树的高度
  private rank: number[] = []

  constructor(size: number = 0) {
    this.parent = new Array(size)

    // 初始化 parent, 表示一个森林, 自己指向自己
    this.rank = new Array(size)
    this.sz = new Array(size)
    for (let i = 0; i < size; i++) {
      this.parent[i] = i
      this.rank[i] = 1
      // 初始化时, 每个节点的 sz 为 1
      this.sz[i] = 1
    }
  }

  /**
   * print
   */
  public print() {
    console.log(this.parent)
    console.log(this.sz)
  }

  /**
   * getSize
   */
  public getSize(): number {
    return this.parent.length
  }

  // 判断两个元素是否在一个集合中: O(h)
  public isConnected(p: number, q: number): boolean {
    return this.findRoot(p) === this.findRoot(q)
  }

  /**
   * unionElements
   */
  public unionElements(p: number, q: number) {
    let pRoot = this.findRoot(p)
    let qRoot = this.findRoot(q)
    if (qRoot === pRoot) {
      return
    }
    this.parent[pRoot] = qRoot
  }

  /**
   * unionElementsForRank
   */
  public unionElementsForRank(p: number, q: number) {
    let pRoot = this.findRoot(p)
    let qRoot = this.findRoot(q)
    if (qRoot === pRoot) {
      return
    }
    // 根据两个元素所在树的高度 rank 不同判断合并方向,
    // 将 rang 低的集合合并到 rank 高的集合上, 保持树的高度
    if (this.rank[pRoot] < this.rank[qRoot]) { // 如果 pRoot 的高度小于 qRoot 的高度,
      this.parent[pRoot] = qRoot // 将 pRoot 挂载在 qRoot 树上
    } else if (this.rank[pRoot] > this.rank[qRoot]) { // 如果 pRoot 的高度大于 qRoot 的高度,
      this.parent[qRoot] = pRoot // 将 qRoot 挂载在 pRoot 树上
    } else {
      this.parent[qRoot] = pRoot // 如果 pRoot 的高度等于 qRoot 的高度,
      this.rank[pRoot] += 1 // 那么随便将谁挂载在谁的上面都可以, 并要更新对应 root 的高度
    }
  }

  // 合并元素 p 和 元素 q 所属的集合: O(h)
  public unionElementsForSz(p: number, q: number): void {
    let pRoot = this.findRoot(p)
    let qRoot = this.findRoot(q)
    if (qRoot === pRoot) {
      return
    }
    // 使用节点少指向节点多个节点
    // 如果 pRoot 的节点数小于 qRoot 的节点数, 那么让 pRoot 指向 qRoot 的节点
    if (this.sz[pRoot] < this.sz[qRoot]) {
      this.parent[pRoot] = qRoot
      // 同时更新 qRoot 的节点数
      this.sz[qRoot] += this.sz[pRoot]
    } else {
      // 如果大于, 说明 pRoot 节点数 大于 qRoot 的节点数, 那么让 qRoot 指向 pRoot 节点数
      this.parent[qRoot] = pRoot
      // 同时更新 pRoot 的节点数
      this.sz[pRoot] += this.sz[qRoot]
    }
  }

  // 查询 p 所对应的集合的编号(根节点): O(h), h 为树的高度
  // 使用 路径压缩 优化查询
  private findRoot(i: number): number {
    if (i < 0 && i >= this.parent.length) {
      throw new Error('i is out of bound')
    }
    while (i !== this.parent[i]) {
      // 这里使用路径压缩来优化查询
      this.parent[i] = this.parent[this.parent[i]]
      i = this.parent[i]
    }
    return i
  }

}
